Field of the Invention
The present invention relates to a hash value generation technique.
Description of the Related Art
To verify whether data has been falsified, a hash value calculated using a cryptographic hash algorithm is used. It has been already proved that SHA-1 as a cryptographic hash algorithm cannot ensure security, and it has been pointed out that security of the SHA-2 family (SHA-224, SHA-256, SHA-384, and SHA-512) may collapse. To solve this problem, the National Institute of Standards and Technology (NIST) sought submissions of new algorithms from the public to stipulate a next generation cryptographic hash algorithm (called SHA-3). The KECCAK algorithm (“The KECCAK reference”, Version 3.0, Jan. 14, 2011, (http://keccak.noekeon.org/Keccak-reference-3.0.pdf) (non-patent literature 1)) was chosen as the SHA-3 algorithm in October 2012.
In SHA-3, four lengths (224 bits, 256 bits, 384 bits, and 512 bits) are defined as the length (size) of a cryptographic hash value to be output. A cryptographic hash value having a fixed length is output for an input message (data) having an arbitrary length. In the KECCAK algorithm, a permutation function of repeating, 24 times, a round process which sequentially applies five steps (θ, ρ, π, χ, and ι) is used. The round process is executed for 1600-bit data called “state”.
In step π included in the round process of the above-described KECCAK algorithm, a parallel process using a data structure called “sheet” or “plane” as a unit is impossible. To increase the speed at which a hash value is generated, a pipeline process may be executed using a data structure called “lane” as a unit. More specifically, except for step π, a two-pipeline structure including steps θ and ρ (to be referred to as θ & ρ hereinafter) and steps χ and ι (to be referred to as χ & ι hereinafter) is plausible.
If, however, a hash value is generated using a lane structure as a unit, it is impossible to perform the parallel operation of the two pipelines of θ & ρ and χ & ι, thereby making it difficult to increase the speed. Furthermore, if a hash value is generated using a lane structure as a unit, it is impossible to start a subsequent round process until all the results of a preceding round process (the entire “state”) are temporarily written in a memory. It is, therefore, impossible to perform the parallel operation of the two pipelines between two continuous round processes, thereby making it difficult to increase the speed.